ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/doc/intervalos.tex

   1 \section{10020 - Minimal coverage}
   2
   3 \textbf{Problema:} dado un conjunto de intervalos $[L_i,R_i)$, determinar
   4 un subconjunto que cubra el segmento $[0,M)$ y que sea m\'inimo
   5 (en el sentido de cardinalidad). En el enunciado los intervalos
   6 se notan $[L,R]$, pero como los extremos son enteros y hay que
   7 cubrir intervalos reales, los problemas son equivalentes.
   8
   9 \subsection{Resolución}
  10 Se resolvi\'o mediante una t\'ecnica golosa. La idea del algoritmo
  11 es tomar en cada paso alguno de los intervalos cuyo borde izquierdo
  12 ya se encuentre cubierto (o a lo sumo coincida con el punto m\'as chico
  13 que todav\'ia no est\'e cubierto) y cuyo borde derecho sea lo mayor posible.
  14
  15 \begin{algorithm}[H]
  16 \begin{algorithmic}
  17 \caption{Subconjunto de $A$ de cardinal m\'inimo que cubre a $[0,M)$}
  18 \PARAMS{$A$: conjunto de intervalos $[L,R)$.}
  19 \ENSURE{ $S$: un conjunto m\'inimo de intervalos de $A$ que cubren $[0,M)$.}
  20 \STATE $A^\star :=$ intervalos no vac\'ios de $A$ ordenados crecientemente por $L$.
  21 \STATE $final := 0$
  22 \STATE $S := [\,]$
  23 \WHILE {$final < M$}
  24   \IF {$A^\star$ es vac\'ia $\lor$ \big($A^\star_0 = [L,R)$ con $L > final$\big)}
  25     \STATE\COMMENT{No se puede cubrir el intervalo $[0,M)$}
  26     \STATE Fallar.
  27   \ELSE
  28     \STATE $C := \{ [L,R) \gets A^\star \text{ tales que } L \leq final \}$
  29     \STATE\COMMENT{$C$ corresponde a un prefijo no vac\'io de $A^\star$}
  30     \STATE $I := [L_I,R_I) \in C$ tal que $R_I = \max\{R : [L,R) \in C\}$
  31     \IF {$R_I \leq final$}
  32       \STATE\COMMENT{No se puede cubrir el intervalo $[0,M)$}
  33       \STATE Fallar.
  34     \ENDIF
  35     \STATE Agregar $I$ a $S$.
  36     \STATE $A^\star := $ sufijo de $A^\star$ omitiendo los primeros $\#C$ elementos
  37     \STATE $final := R_I$
  38   \ENDIF
  39 \ENDWHILE
  40 \end{algorithmic}
  41 \end{algorithm}
  42
  43 El algoritmo termina porque el conjunto $C$ nunca es vac\'io, y por lo tanto $A^\star$
  44 se va achicando.
  45 El invariante del algoritmo es que los intervalos en $S$ cubren el
  46 intervalo $[0,final)$.
  47 Al entrar en una iteraci\'on, todav\'ia falta cubrir el intervalo
  48 $[final, M)$. En la rama del {\bf then}, no se puede cubrir
  49 $[final, M)$ y por lo tanto tampoco $[0,M)$.
  50
  51 En la rama del {\bf else}, el conjunto $C$ no es vac\'io.
  52 Corresponde a un prefijo de $A^\star$ porque los elementos de $A^\star$
  53 est\'an ordenados. Si hay soluci\'on, al menos un intervalo de $C$ debe
  54 figurar en ella, porque todos los intervalos restantes de $A^\star$ no
  55 cubren el punto $final$. Se puede encontrar una soluci\'on m\'inima
  56 tomando $I$ como alguno de los intervalos de $C$ cuyo extremo
  57 derecho sea mayor.
  58 Al incluir $I$ en la soluci\'on, todos los dem\'as intervalos
  59 de $C$ quedan cubiertos por el contenido de $S$ y por lo tanto
  60 se pueden excluir de $A^\star$.
  61
  62 Adem\'as, incluir $I$ en la soluci\'on no puede ser una mala
  63 decisi\'on (que ``moleste'' en iteraciones posteriores), porque
  64 el hecho de elegir un valor m\'as grande de $R_I$ hace que
  65 en iteraciones posteriores el valor de $final$ sea mayor y
  66 por lo tanto el conjunto $C$ incluya m\'as intervalos.
  67
  68 Para una entrada de $n$ intervalos, la complejidad del algoritmo
  69 es $O(n \log n)$ en peor caso. El paso m\'as costoso es ordenarlos.
  70 El resto del algoritmo se reduce a
  71 hacer una pasada sobre los intervalos ya ordenados\footnote{
  72 Eventualmente se podr\'ia mejorar la complejidad para que ordenarlos
  73 fuera $O(n)$ haciendo bucket sort. El enunciado afirma que el valor
  74 de los extremos $L_i, R_i$ es a lo sumo $50000$. Pueden ser negativos,
  75 pero para este problema ser\'ia equivalente considerar los
  76 intervalos $[\max(L_i,0),\max(R_i,0))$.
  77 }. Al iterar los intervalos ordenados según su primera componente, no es
  78 necesario construir los $C$ de forma expl\'icita. Simplemente se recorre hasta
  79 que se obtiene el primer intervalo que cumple que $L_i > final$. El máximo
  80 $R_i$ que actualiza a $final$ se puede obtener durante la recorrida. Luego
  81 alcanza con seguir iterando desde donde se terminó, ya que los intervalos ya
  82 revisados no son candidatos a tener en cuenta. Como la lista de intervalos se
  83 recorre a lo sumo una sola vez, el ciclo itera $O(n)$ veces,
  84 con lo cual el costo que domina es el de ordenar los intervalos.
  85
  86 Las operaciones para manipular intervalos son $O(1)$ porque
  87 los extremos se representan con enteros de 32 bits.
  88
  89 En la implementaci\'on del algoritmo en C++ no se incluye el {\bf if}
  90 cuya condici\'on es $R_I \leq final$. En ese caso, el
  91 algoritmo falla en la siguiente iteraci\'on, porque si
  92 $A^\star$ no es vac\'ia, el primer intervalo no puede ser
  93 tal que $L \leq final$.
  94
  95 \subsection{Implementación}
  96
  97 \noindent
  98 \ttfamily
  99 \shorthandoff{"}\\
 100 \hlstd{}\hlline{\ 1\ }\hldir{\#include\ $<$stdio.h$>$}\\
 101 \hlline{\ 2\ }\hlstd{}\hldir{\#include\ $<$iostream$>$}\\
 102 \hlline{\ 3\ }\hlstd{}\hldir{\#include\ $<$list$>$}\\
 103 \hlline{\ 4\ }\hlstd{}\\
 104 \hlline{\ 5\ }\hlkwa{using\ namespace\ }\hlstd{std}\hlsym{;}\\
 105 \hlline{\ 6\ }\hlstd{}\\
 106 \hlline{\ 7\ }\hldir{\#define\ foreachin(it,s)\ for\ (typeof(s.begin())\ it\ =\ (s).begin();\ it\ !=\ (s).end();\ it++)}\\
 107 \hlline{\ 8\ }\hlstd{}\\
 108 \hlline{\ 9\ }\hlkwc{typedef\ }\hlstd{pair}\hlsym{$<$}\hlstd{}\hlkwb{int}\hlstd{}\hlsym{,\ }\hlstd{}\hlkwb{int}\hlstd{}\hlsym{$>$\ }\hlstd{Intervalo}\hlsym{;}\\
 109 \hlline{10\ }\hlstd{}\hlkwc{typedef\ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\ }\hlstd{LIntervalo}\hlsym{;}\\
 110 \hlline{11\ }\hlstd{}\\
 111 \hlline{12\ }\hlkwb{bool\ }\hlstd{}\hlkwd{compararPorPrimeraComp}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{Intervalo}\hlsym{\&\ }\hlstd{p1}\hlsym{,\ }\hlstd{}\hlkwb{const\ }\hlstd{Intervalo}\hlsym{\&\ }\hlstd{p2}\hlsym{)\{}\\
 112 \hlline{13\ }\hlstd{\ }\hlkwa{return\ }\hlstd{p1}\hlsym{.}\hlstd{first\ }\hlsym{$<$\ }\hlstd{p2}\hlsym{.}\hlstd{first}\hlsym{;}\\
 113 \hlline{14\ }\hlstd{}\hlsym{\}}\\
 114 \hlline{15\ }\hlstd{}\\
 115 \hlline{16\ }\hlkwb{bool\ }\hlstd{}\hlkwd{resolver}\hlstd{}\hlsym{(}\hlstd{LIntervalo}\hlsym{\&\ }\hlstd{intervalos}\hlsym{,\ }\hlstd{}\hlkwb{int\ }\hlstd{limite}\hlsym{,\ }\hlstd{LIntervalo}\hlsym{\&\ }\hlstd{solucion}\hlsym{)\ \{}\\
 116 \hlline{17\ }\hlstd{\ intervalos}\hlsym{.}\hlstd{}\hlkwd{sort}\hlstd{}\hlsym{(}\hlstd{compararPorPrimeraComp}\hlsym{);}\\
 117 \hlline{18\ }\hlstd{\ }\hlkwb{int\ }\hlstd{final\ }\hlsym{=\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{;\ }\hlstd{}\hlslc{//\ mayor\ coordenada\ cubierta\ hasta\ ahora}\\
 118 \hlline{19\ }\hlstd{\ }\hlkwb{int\ }\hlstd{r\textunderscore i\ }\hlsym{=\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{;}\hlstd{\ \ \ }\hlsym{}\hlstd{}\hlslc{//\ mayor\ coordenada\ hasta\ ahora\ alcanzada}\\
 119 \hlline{20\ }\hlstd{\ Intervalo\ parActual\ }\hlsym{=\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{);\ }\hlstd{}\hlslc{//\ posible\ candidato\ a\ ser\ agregado}\\
 120 \hlline{21\ }\hlstd{\\
 121 \hlline{22\ }\ }\hlkwd{foreachin\ }\hlstd{}\hlsym{(}\hlstd{it}\hlsym{,\ }\hlstd{intervalos}\hlsym{)\ \{}\\
 122 \hlline{23\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlslc{//\ si\ la\ primera\ componente\ esta\ mayor\ que\ final,\ ya\ miramos}\\
 123 \hlline{24\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlslc{//\ todo\ el\ C,\ entonces\ hay\ que\ agregar\ el\ intervalo}\\
 124 \hlline{25\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{it}\hlsym{{-}$>$}\hlstd{first\ }\hlsym{$>$\ }\hlstd{final}\hlsym{)\ \{}\\
 125 \hlline{26\ }\hlstd{}\hlstd{\ \ \ }\hlstd{solucion}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{parActual}\hlsym{);}\\
 126 \hlline{27\ }\hlstd{}\hlstd{\ \ \ }\hlstd{final\ }\hlsym{=\ }\hlstd{r\textunderscore i}\hlsym{;\ }\hlstd{}\hlslc{//\ muevo\ el\ borde\ final}\\
 127 \hlline{28\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlsym{\}}\\
 128 \hlline{29\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlslc{//\ si\ la\ primera\ componente\ es\ menor\ que\ final\ miro\ si\ el\ intervalo\ sirve}\\
 129 \hlline{30\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{it}\hlsym{{-}$>$}\hlstd{first\ }\hlsym{$<$=\ }\hlstd{final}\hlsym{)\ \{}\\
 130 \hlline{31\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlslc{//\ sirve\ si\ llega\ mas\ lejos\ que\ lo\ que\ hay\ hasta\ ahora}\\
 131 \hlline{32\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{it}\hlsym{{-}$>$}\hlstd{second\ }\hlsym{$>$\ }\hlstd{r\textunderscore i}\hlsym{)\ \{}\\
 132 \hlline{33\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{r\textunderscore i\ }\hlsym{=\ }\hlstd{it}\hlsym{{-}$>$}\hlstd{second}\hlsym{;}\\
 133 \hlline{34\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{parActual\ }\hlsym{=\ {*}}\hlstd{it}\hlsym{;}\\
 134 \hlline{35\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlslc{//\ si\ ademas\ ya\ llegue\ al\ limite,\ termine}\\
 135 \hlline{36\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{r\textunderscore i\ }\hlsym{$>$=\ }\hlstd{limite}\hlsym{)\ \{}\\
 136 \hlline{37\ }\hlstd{}\hlstd{\ \ \ \ \ }\hlstd{solucion}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{parActual}\hlsym{);}\\
 137 \hlline{38\ }\hlstd{}\hlstd{\ \ \ \ \ }\hlstd{}\hlkwa{break}\hlstd{}\hlsym{;}\\
 138 \hlline{39\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}\ }\\
 139 \hlline{40\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlsym{\}}\\
 140 \hlline{41\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ }\hlstd{}\hlsym{\{}\\
 141 \hlline{42\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlslc{//\ hay\ un\ hueco\ que\ no\ puedo\ cubrir\ con\ ningun\ intervalo}\\
 142 \hlline{43\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlkwa{break}\hlstd{}\hlsym{;}\\
 143 \hlline{44\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlsym{\}}\\
 144 \hlline{45\ }\hlstd{\ }\hlsym{\}}\\
 145 \hlline{46\ }\hlstd{\\
 146 \hlline{47\ }\ }\hlkwa{return\ }\hlstd{r\textunderscore i\ }\hlsym{$>$=\ }\hlstd{limite}\hlsym{;}\\
 147 \hlline{48\ }\hlstd{}\hlsym{\}}\\
 148 \hlline{49\ }\hlstd{}\\
 149 \hlline{50\ }\hlkwb{int\ }\hlstd{}\hlkwd{main}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{int\ }\hlstd{argc}\hlsym{,\ }\hlstd{}\hlkwb{char\ }\hlstd{}\hlsym{{*}{*}}\hlstd{argv}\hlsym{)}\\
 150 \hlline{51\ }\hlstd{}\hlsym{\{}\\
 151 \hlline{52\ }\hlstd{\ }\hlkwb{int\ }\hlstd{casos}\hlsym{;}\\
 152 \hlline{53\ }\hlstd{\ cin\ }\hlsym{$>$$>$\ }\hlstd{casos}\hlsym{;}\\
 153 \hlline{54\ }\hlstd{\ }\hlkwa{while\ }\hlstd{}\hlsym{(}\hlstd{casos\ }\hlsym{$>$\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \{}\\
 154 \hlline{55\ }\hlstd{}\hlstd{\ \ }\hlstd{casos}\hlsym{{-}{-};}\\
 155 \hlline{56\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwb{int\ }\hlstd{limite}\hlsym{,\ }\hlstd{x}\hlsym{,\ }\hlstd{y}\hlsym{;}\\
 156 \hlline{57\ }\hlstd{}\hlstd{\ \ }\hlstd{cin\ }\hlsym{$>$$>$\ }\hlstd{limite}\hlsym{;}\\
 157 \hlline{58\ }\hlstd{}\hlstd{\ \ }\hlstd{x\ }\hlsym{=\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{;}\\
 158 \hlline{59\ }\hlstd{}\hlstd{\ \ }\hlstd{y\ }\hlsym{=\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{;}\\
 159 \hlline{60\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlslc{//\ cargo\ intervalos}\\
 160 \hlline{61\ }\hlstd{}\hlstd{\ \ }\hlstd{LIntervalo\ intervalos}\hlsym{;}\\
 161 \hlline{62\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{while\ }\hlstd{}\hlsym{(}\hlstd{y\ }\hlsym{!=\ }\hlstd{}\hlnum{0\ }\hlstd{}\hlsym{\textbar \textbar \ }\hlstd{x\ }\hlsym{!=\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \{}\\
 162 \hlline{63\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlkwd{scanf\ }\hlstd{}\hlsym{(}\hlstd{}\hlstr{"\%d\ \%d"}\hlstd{}\hlsym{,\ \&}\hlstd{x}\hlsym{,\ \&}\hlstd{y}\hlsym{);}\\
 163 \hlline{64\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{x\ }\hlsym{!=\ }\hlstd{}\hlnum{0\ }\hlstd{}\hlsym{\textbar \textbar \ }\hlstd{y\ }\hlsym{!=\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \{}\\
 164 \hlline{65\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{x\ }\hlsym{$<$\ }\hlstd{y}\hlsym{)\ \{\ }\hlstd{}\hlslc{//para\ no\ cargar\ intervalos\ inutiles}\\
 165 \hlline{66\ }\hlstd{}\hlstd{\ \ \ \ \ }\hlstd{intervalos}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore front}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{x}\hlsym{,}\hlstd{y}\hlsym{));}\\
 166 \hlline{67\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 167 \hlline{68\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlsym{\}}\\
 168 \hlline{69\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlsym{\}}\\
 169 \hlline{70\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlslc{//\ resuelvo\ instancia}\\
 170 \hlline{71\ }\hlstd{}\hlstd{\ \ }\hlstd{LIntervalo\ solucion}\hlsym{;}\\
 171 \hlline{72\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{}\hlkwd{resolver}\hlstd{}\hlsym{(}\hlstd{intervalos}\hlsym{,\ }\hlstd{limite}\hlsym{,\ }\hlstd{solucion}\hlsym{))\ \{}\\
 172 \hlline{73\ }\hlstd{}\hlstd{\ \ \ }\hlstd{cout\ }\hlsym{$<$$<$\ }\hlstd{solucion}\hlsym{.}\hlstd{}\hlkwd{size}\hlstd{}\hlsym{()\ $<$$<$\ }\hlstd{endl}\hlsym{;}\\
 173 \hlline{74\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlkwd{foreachin\ }\hlstd{}\hlsym{(}\hlstd{it}\hlsym{,\ }\hlstd{solucion}\hlsym{)\ \{}\\
 174 \hlline{75\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{cout\ }\hlsym{$<$$<$\ }\hlstd{it}\hlsym{{-}$>$}\hlstd{first\ }\hlsym{$<$$<$\ }\hlstd{}\hlstr{"\ "}\hlstd{\ }\hlsym{$<$$<$\ }\hlstd{it}\hlsym{{-}$>$}\hlstd{second\ }\hlsym{$<$$<$\ }\hlstd{endl}\hlsym{;}\\
 175 \hlline{76\ }\hlstd{}\hlstd{\ \ \ }\hlstd{}\hlsym{\}}\\
 176 \hlline{77\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ }\hlstd{}\hlsym{\{}\\
 177 \hlline{78\ }\hlstd{}\hlstd{\ \ \ }\hlstd{cout\ }\hlsym{$<$$<$\ }\hlstd{}\hlnum{0\ }\hlstd{}\hlsym{$<$$<$\ }\hlstd{endl}\hlsym{;}\\
 178 \hlline{79\ }\hlstd{}\hlstd{\ \ }\hlstd{}\hlsym{\}}\\
 179 \hlline{80\ }\hlstd{}\hlstd{\ \ }\hlstd{cout\ }\hlsym{$<$$<$\ }\hlstd{endl}\hlsym{;}\\
 180 \hlline{81\ }\hlstd{\ }\hlsym{\}}\\
 181 \hlline{82\ }\hlstd{}\hlsym{\}}\\
 182 \hlline{83\ }\hlstd{}\\
 183 \mbox{}
 184 \normalfont
 185 \shorthandon{"}
 186
 187